﻿//https://leetcode.cn/problems/minimum-window-substring/
//我的
//用一个队列来记录有效位置，减少left下一跳的时间，但是由于是用空间换时间，导致内存溢出了QAQ
class Solution {
public:
    string minWindow(string s, string t) {
        int tHash[128] = { 0 };//记录目标期间
        for (auto tmp : t)tHash[tmp]++;
        //寻找一个有效位置
        int left = 0;
        list<int> pos;
        int windowHash[128] = { 0 };//记录当前区间
        string ret;
        for (int i = 0; i < s.size();) {
            if (tHash[s[i]] != 0) {
                left = i;
                pos.push_back(left);
                windowHash[s[left]]++;
                break;
            }
            ++i;
            left = i;
        }
        for (int right = left + 1, count = 1; left < s.size();) {
            //进窗口
            while (right < s.size() && count < t.size()) {
                char cur = s[right];
                if (tHash[cur] != 0)//只对有效字符处理
                {
                    windowHash[cur]++;
                    pos.push_back(right);
                    if (windowHash[cur] <= tHash[cur])count++;
                }
                right++;
            }
            //判断
            if (count == t.size()) {
                string tmp(s.begin() + pos.front(), s.begin() + pos.back() + 1);
                if (ret.size() > tmp.size() || ret.empty())ret = tmp;
            }

            //出窗口
            if (pos.size() >= t.size()) {
                char out = s[pos.front()];
                if (windowHash[out] <= tHash[out])count--;
                windowHash[out]--;
                pos.pop_front();
                left = pos.front();
            }
            else break;//为空，没有有效位置
        }
        return ret;
    }
};

class Solution
{
public:
	string minWindow(string s, string t)
	{
		int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
		int kinds = 0; // 统计有效字符有多少种
		for (auto ch : t)
			if (hash1[ch]++ == 0) kinds++;
		int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
		int minlen = INT_MAX, begin = -1;
		for (int left = 0, right = 0, count = 0; right < s.size(); right++)
		{
			char in = s[right];
			if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
			while (count == kinds) // 判断条件
			{
				if (right - left + 1 < minlen) // 更新结果
				{
					minlen = right - left + 1;
					begin = left;
				}
				char out = s[left++];
				if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
			}
		}
		if (begin == -1) return "";
		else return s.substr(begin, minlen);
	}
};